/**
* 大数阶乘运算
* 主要参考了这边博客https://blog.csdn.net/wuzhekai1985/article/details/6845868
* 加上了自己的理解和注释
* 注释的目的旨在几年后的的自己花上很短的时间就能回顾该算法

* 问题描述：求一个整数 n 的阶乘，0 <= n <=5000。
     比如n = 50，结果为30414093201713378043612608166064768844377641568960512000000000000
*/




/** 
 一个例子
 考虑小学的时候学的乘法运算的手算方法

                   1 2 3 4
                 * 5 6 7 8
--------------------------------
                   9 8 7 2
                 8 6 3 8
               7 4 0 4
             6 1 7 0
--------------------------------
             1 2 1 1 1
--------------------------------
             7 0 0 6 6 5 2
我们只需要依次计算出 7 0 0 6 6 5 2 并保存到数组中即可

假设原来数组A中存放的4个元素是 4 3 2 1
该数组表示一个大数 1234，其中权重大的数放在数组的后面
现在需要将该数 乘以 5678 
可以首先用 4*4578 得到 22712 ,此时模10 运算得到了最低位，即数组 A[0] = 22712%10 =2
同时得到进位 22712 / 10 = 2271，
接下来计算A[1] 的值 3* 5678 + 2271 = 19305 ，因为A[1] 只能存放一位，因此，A[1] = 19305%10 = 5
进位为 19305/10 = 1930
接下来计算A[2] 的值 2*5678 + 1930 = 13286 ，同样，保存A[2] = 13286%10 = 6
进位为 13286 / 10 = 1328
接下来计算A[3] 的值 1*5678 + 1328 = 7006 ，同样，保存A[3] = 7006%10 = 6
进位为 7006 / 10 = 700
A[4] = (0*5678 + 700) % 10 = 0 ,进位70
A[5] = (0*5678 + 70) % 10 = 0,进位7
A[6] = (0*5678 + 7) %10 = 7,进位0；
A[4]~A[6] 也可以直接将刚才得到的进位保存进去
然后从A[6] 往前打印A，得到7006652

接下来我们将上述的乘法过程交换一下
                   5 6 7 8
                *  1 2 3 4
--------------------------------
   =             2 2 7 1 2
               1 7 0 3 4
             1 1 3 5 6
             5 6 7 8
--------------------------------
             1 2 1 1 
--------------------------------
             7 0 0 6 6 5 2

再细分一下
                   5 6 7 8
                *  1 2 3 4
--------------------------------
   =             2 2 7 1 2
          +    1 7 0 3 4
          +  1 1 3 5 6
          +  5 6 7 8
-------------------------------- 前两行相加
   =           1 9 3 0 5 2
          +  1 1 3 5 6
          +  5 6 7 8
-------------------------------- 前两行相加
   =         1 3 2 8 6 5 2
          +  5 6 7 8
--------------------------------
             7 0 0 6 6 5 2
这就是该算法的数学原理

*/

#include <iostream>
#include <stdio.h>
using namespace std;

int way1(int n)
{
	int a[20000] = {1,0};		//初始时，数字为1
	int m = 0;					//m保存a中有效的位数的索引
	int c = 0; 					//进位值
	int temp = 0;
	for(; n>0; n--)				//依次乘n,n-1,...,1
	{
		c = 0;
		//中间结果乘n； 大数乘法操作
		//计算对应于上面例子中的A[0] ~ A[3]
		for(int i=0; i<=m; i++)	
		{
			temp = a[i]*n + c;		
			a[i] = temp %10;
			c = temp/10;
		}
		//计算对应于上面例子中的A[4] ~ A[6]
		for(; c>0; c/=10)
			a[++m] = c%10;
	}
	for(int i=m; i>=0; i--)
		cout << a[i];
	cout << endl;
	return m+1;					//结果的位数
}


//方法一中，数组的每个元素只保存1位，而事实上，每一个数组元素可以保存多位
//可以将方法一看做是10进制数
//以下方法二可以看做是 10000 进制数，该方法与方法一思路完全相同
int way2(int n)
{
	int a[5000] = {1,0};		//初始时，数字为1
	int m = 0;					//m保存a中有效的位数的索引
	int c = 0; 					//进位值
	int temp = 0;
	for(; n>0; n--)				//依次乘n,n-1,...,1
	{
		c = 0;
		//中间结果乘n； 大数乘法操作
		//计算对应于上面例子中的A[0] ~ A[3]
		for(int i=0; i<=m; i++)	
		{
			temp = a[i]*n + c;		
			a[i] = temp %10000;
			c = temp/10000;
		}
		//计算对应于上面例子中的A[4] ~ A[6]
		for(; c>0; c/=10000)
			a[++m] = c%10000;
	}
	
	printf("%d",a[m]);
	for(int i=m-1; i>=0; i--)
		//如果不设置显示宽度的话，有些数字前面的0不会打印
		//cout << setw(4) << setfill('0') << a[i];
		printf("%04d",a[i]);
	cout << endl;
	return m+1;					//结果的位数
}


/**
* 对方法2，我们同样举一个例子
我们考虑100进制的情况，而不是方法二中的10000进制的情况，然后类比就好了
                   5 6 7 8
               *   1 2 3 4  其中(一十二存放在A[1]中，三十四存放在A[0]中)
--------------------------------
               1 9 3 0 5 2   =(34*5678)
             6 8 1 3 6       =(12*5678)
--------------------------------
             7 0 0 6 6 5 2   =(12*5678+34*5678%100) || (34*5678/100)     (||为连字符) 
*/



int main(int argc, char* argv[])
{
	int n;
	int value_ret = 0;
	cin >> n;
	cout << "way1" << endl;
	value_ret = way1(n);
	cout << "retun value is " << value_ret << endl << endl;
	cout << "way2" <<endl;
	value_ret = way2(n);
	cout << "retun value is " << value_ret << endl << endl;
	return 0;
}























